package com.yanceysong.codetop.s31_s40;


public class S38_Hard_4_寻找两个正序数组的中位数 {
    /**
     * 题目：寻找两个正序数组的中位数 (Median of Two Sorted Arrays)
     * LeetCode: <a href="https://leetcode.cn/problems/median-of-two-sorted-arrays/">...</a>
     * 难度：Hard
     * ------------------------------------------------------------
     * 给定两个大小分别为 m 和 n 的 有序（非降序）整数数组 nums1 和 nums2。
     * 请你找出并返回这两个数组的 中位数 。算法的时间复杂度应该为 O(log (m+n))。
     * <p>
     * 中位数定义：
     * . 当合并后数组长度 L 为奇数：中位数 = 第 (L/2 + 1) 小的元素 (1-based)
     * . 当合并后数组长度 L 为偶数：中位数 = (第 L/2 小 + 第 L/2 + 1 小的元素) / 2
     * <p>
     * 示例1：
     * . 输入：nums1 = [1,3], nums2 = [2]
     * . 合并：[1,2,3]  -> 中位数 = 2
     * . 输出：2.00000
     * <p>
     * 示例2：
     * . 输入：nums1 = [1,2], nums2 = [3,4]
     * . 合并：[1,2,3,4] -> 中位数 = (2 + 3) / 2 = 2.5
     * . 输出：2.50000
     * <p>
     * 示例3（一个数组为空）：
     * . 输入：nums1 = [], nums2 = [2,3]
     * . 合并：[2,3] -> 中位数 = (2+3)/2 = 2.5
     * . 输出：2.50000
     * <p>
     * ------------------------------------------------------------
     * 解题核心思想（对数时间的“第 k 小”淘汰法 / 二分缩小搜索范围）:
     * 我们不真正合并两个数组（那样是 O(m+n)），而是“同时跳过”某些不可能成为答案的前缀。
     * 设要找第 k 小元素，我们比较两个数组当前指针后 k/2 位置的元素（称为 pivot），然后淘汰较小 pivot 所在数组的前半段（含该 pivot），因为这些元素最多也只能排在前 (k/2) 个之内，不可能是第 k 小。
     * 每次淘汰至少 k/2 个元素，k 迅速减小，故总时间 O(log(m+n))。
     * <p>
     * ------------------------------------------------------------
     * ASCII 过程示意：寻找第 k 小
     * <p>
     * .nums1:  a1  a2  a3  a4  a5  ...
     * .         ^          ^
     * .         |          |__ probeIndex1 (index1 + half - 1)
     * .         |__ index1 (当前还未淘汰的起点)
     * <p>
     * .nums2:  b1  b2  b3  b4  b5  ...
     * .         ^          ^
     * .         |          |__ probeIndex2
     * .         |__ index2
     * <p>
     * half = k/2
     * pivot1 = nums1[probeIndex1]
     * pivot2 = nums2[probeIndex2]
     * 如果 pivot1 <= pivot2 -> 淘汰 nums1[index1 ... probeIndex1]
     * 否则淘汰 nums2[index2 ... probeIndex2]
     * <p>
     * 不变量：在每一轮循环开始时，我们总是要在 nums1[index1 ...] 与 nums2[index2 ...] 的未淘汰部分中寻找第 k 小元素。
     * ------------------------------------------------------------
     * 关键洞察 / Why it works：
     * 1. 至少淘汰 ⌊k/2⌋ 个：保证对数层数。
     * 2. 安全淘汰：被淘汰段长度 <= ⌊k/2⌋，故目标第 k 小不可能在其中。
     * 3. 边界收敛：某数组被完全淘汰后，直接在另一个数组定位即可。
     * 4. k==1 兜底：相当于合并序列的第一个元素。
     * <p>
     * ------------------------------------------------------------
     * 复杂度：
     * . 时间 O(log(m+n))  （k 以至少 /2 速度下降）
     * . 空间 O(1)
     */
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int length1 = nums1.length, length2 = nums2.length;
        int totalLength = length1 + length2;
        if (totalLength == 0) {
            throw new IllegalArgumentException("Both input arrays are empty – median undefined");
        }
        // 奇数：找第 (totalLength/2 + 1) 小
        if (totalLength % 2 == 1) {
            int kth = totalLength / 2 + 1; // 1-based
            return getKthElement(nums1, nums2, kth);
        } else {
            // 偶数：平均第 totalLength/2 与 totalLength/2 + 1 小
            int k1 = totalLength / 2;
            int k2 = totalLength / 2 + 1;
            return (getKthElement(nums1, nums2, k1) + getKthElement(nums1, nums2, k2)) / 2.0;
        }
    }

    /**
     * 查找两个已排序数组的第 k (1-based) 小的元素。
     * Contract:
     * Inputs: nums1, nums2 升序; 1 <= k <= nums1.length + nums2.length; 至少一个数组非空。
     * Output: 对应第 k 小值。
     * Edge Cases Covered: 某数组耗尽 / k==1 / k 跨越数组剩余长度。
     */
    public int getKthElement(int[] nums1, int[] nums2, int k) {
        int length1 = nums1.length, length2 = nums2.length;
        int index1 = 0, index2 = 0; // 当前未淘汰区间的起点

        while (true) {
            // Case 1: nums1 耗尽 -> 直接在 nums2 中取
            if (index1 == length1) {
                return nums2[index2 + k - 1];
            }
            // Case 2: nums2 耗尽 -> 直接在 nums1 中取
            if (index2 == length2) {
                return nums1[index1 + k - 1];
            }
            // Case 3: 找第 1 小 -> 取两个当前首元素较小者
            if (k == 1) {
                return Math.min(nums1[index1], nums2[index2]);
            }

            int half = k / 2; // 本轮计划跳过的数量（来自两数组合计）
            // 试探位置：向前 half，但不得越界（不足时用数组末尾替代）
            int probeIndex1 = Math.min(index1 + half, length1) - 1; // 0-based
            int probeIndex2 = Math.min(index2 + half, length2) - 1;
            int pivot1 = nums1[probeIndex1];
            int pivot2 = nums2[probeIndex2];

            if (pivot1 <= pivot2) {
                // 淘汰 nums1[index1 .. probeIndex1]
                int eliminated = probeIndex1 - index1 + 1;
                k -= eliminated;
                index1 = probeIndex1 + 1;
            } else {
                // 淘汰 nums2[index2 .. probeIndex2]
                int eliminated = probeIndex2 - index2 + 1;
                k -= eliminated;
                index2 = probeIndex2 + 1;
            }
        }
    }

    // ====================== 测试代码区域 (main) ======================
    public static void main(String[] args) {
        S38_Hard_4_寻找两个正序数组的中位数 solver = new S38_Hard_4_寻找两个正序数组的中位数();

        System.out.println("=== 寻找两个正序数组的中位数 测试开始 ===");

        // 1. 题目示例测试
        System.out.println("\n--- 测试1: 题目示例 (奇数长度) ---");
        testExample1(solver);

        System.out.println("\n--- 测试2: 题目示例 (偶数长度) ---");
        testExample2(solver);

        // 2. 一个数组为空的情况
        System.out.println("\n--- 测试3: 一个数组为空 ---");
        testOneArrayEmpty(solver);

        // 3. 含重复元素
        System.out.println("\n--- 测试4: 含重复元素 ---");
        testWithDuplicates(solver);

        // 4. 含负数
        System.out.println("\n--- 测试5: 含负数 ---");
        testWithNegatives(solver);

        // 5. 多组随机测试（正确性鲁棒性）
        System.out.println("\n--- 测试6: 随机压力测试 (100轮) ---");
        randomStressTest(solver, 100);

        // 6. 边界：两个数组都空 -> 应抛异常
        System.out.println("\n--- 测试7: 双空数组异常检查 ---");
        testBothEmptyShouldThrow(solver);

        // 7. 长度差异极大
        System.out.println("\n--- 测试8: 长度差异极大 ---");
        testHighlyUnbalanced(solver);

        // 8. 交错排列验证
        System.out.println("\n--- 测试9: 交错分布数组 ---");
        testInterleaving(solver);

        System.out.println("\n=== 所有测试完成 ===");
    }

    // ========== 辅助断言方法 ==========
    private static void assertDoubleEquals(double actual, double expected, double eps, String message) {
        if (Double.isNaN(actual) || Math.abs(actual - expected) > eps) {
            throw new AssertionError(message + " | actual=" + actual + ", expected=" + expected);
        }
    }

    // ========== 单独测试方法 ==========
    private static void testExample1(S38_Hard_4_寻找两个正序数组的中位数 solver) {
        int[] a = {1, 3};
        int[] b = {2};
        double ans = solver.findMedianSortedArrays(a, b);
        System.out.println("输入: [1,3] & [2] -> 输出: " + ans + " (期望: 2.0)");
        assertDoubleEquals(ans, 2.0, 1e-9, "示例1失败");
        System.out.println("✓ 示例1通过");
    }

    private static void testExample2(S38_Hard_4_寻找两个正序数组的中位数 solver) {
        int[] a = {1, 2};
        int[] b = {3, 4};
        double ans = solver.findMedianSortedArrays(a, b);
        System.out.println("输入: [1,2] & [3,4] -> 输出: " + ans + " (期望: 2.5)");
        assertDoubleEquals(ans, 2.5, 1e-9, "示例2失败");
        System.out.println("✓ 示例2通过");
    }

    private static void testOneArrayEmpty(S38_Hard_4_寻找两个正序数组的中位数 solver) {
        int[] a1 = {};
        int[] b1 = {1};
        double ans1 = solver.findMedianSortedArrays(a1, b1);
        System.out.println("输入: [] & [1] -> 输出: " + ans1 + " (期望: 1.0)");
        assertDoubleEquals(ans1, 1.0, 1e-9, "空数组案例1失败");

        int[] a2 = {};
        int[] b2 = {2, 3};
        double ans2 = solver.findMedianSortedArrays(a2, b2);
        System.out.println("输入: [] & [2,3] -> 输出: " + ans2 + " (期望: 2.5)");
        assertDoubleEquals(ans2, 2.5, 1e-9, "空数组案例2失败");

        int[] a3 = {5};
        int[] b3 = {};
        double ans3 = solver.findMedianSortedArrays(a3, b3);
        System.out.println("输入: [5] & [] -> 输出: " + ans3 + " (期望: 5.0)");
        assertDoubleEquals(ans3, 5.0, 1e-9, "空数组案例3失败");
        System.out.println("✓ 一个数组为空测试通过");
    }

    private static void testWithDuplicates(S38_Hard_4_寻找两个正序数组的中位数 solver) {
        int[] a = {1, 1, 1};
        int[] b = {1, 1};
        double ans = solver.findMedianSortedArrays(a, b); // 全部为1
        System.out.println("输入: [1,1,1] & [1,1] -> 输出: " + ans + " (期望: 1.0)");
        assertDoubleEquals(ans, 1.0, 1e-9, "重复元素测试失败");
        System.out.println("✓ 重复元素测试通过");
    }

    private static void testWithNegatives(S38_Hard_4_寻找两个正序数组的中位数 solver) {
        int[] a = {-5, -3, -1};
        int[] b = {-4, -2};
        double ans = solver.findMedianSortedArrays(a, b); // 合并 [-5,-4,-3,-2,-1] -> -3
        System.out.println("输入: [-5,-3,-1] & [-4,-2] -> 输出: " + ans + " (期望: -3.0)");
        assertDoubleEquals(ans, -3.0, 1e-9, "负数测试失败");
        System.out.println("✓ 负数测试通过");
    }

    private static void randomStressTest(S38_Hard_4_寻找两个正序数组的中位数 solver, int rounds) {
        java.util.Random rand = new java.util.Random(42);
        for (int r = 1; r <= rounds; r++) {
            int lenA = rand.nextInt(10);  // 0-9
            int lenB = rand.nextInt(10);  // 0-9
            if (lenA + lenB == 0) { // 保证至少一个非空
                lenA = 1;
            }
            int[] a = new int[lenA];
            int[] b = new int[lenB];
            for (int i = 0; i < lenA; i++) a[i] = rand.nextInt(50) - 25; // [-25,24]
            for (int i = 0; i < lenB; i++) b[i] = rand.nextInt(50) - 25;
            java.util.Arrays.sort(a);
            java.util.Arrays.sort(b);

            double ans = solver.findMedianSortedArrays(a, b);
            double baseline = baselineMedian(a, b);
            assertDoubleEquals(ans, baseline, 1e-9, "随机测试第" + r + "轮失败");
        }
        System.out.println("随机测试共 " + rounds + " 轮全部通过");
    }

    private static double baselineMedian(int[] a, int[] b) {
        int[] merged = new int[a.length + b.length];
        int i = 0, j = 0, k = 0;
        while (i < a.length && j < b.length) {
            if (a[i] <= b[j]) merged[k++] = a[i++];
            else merged[k++] = b[j++];
        }
        while (i < a.length) merged[k++] = a[i++];
        while (j < b.length) merged[k++] = b[j++];
        int n = merged.length;
        if (n % 2 == 1) return merged[n / 2];
        return (merged[n / 2 - 1] + merged[n / 2]) / 2.0;
    }

    private static void testBothEmptyShouldThrow(S38_Hard_4_寻找两个正序数组的中位数 solver) {
        int[] a = {};
        int[] b = {};
        boolean thrown = false;
        try {
            solver.findMedianSortedArrays(a, b);
        } catch (IllegalArgumentException e) {
            thrown = true;
            System.out.println("调用双空数组抛出期望异常: " + e.getMessage());
        }
        if (!thrown) {
            throw new AssertionError("双空数组应当抛出异常但没有");
        }
        System.out.println("✓ 双空数组异常测试通过");
    }

    private static void testHighlyUnbalanced(S38_Hard_4_寻找两个正序数组的中位数 solver) {
        int[] longArr = new int[101];
        for (int i = 0; i < 101; i++) longArr[i] = i * 2; // 偶数序列 0,2,4,...
        int[] shortArr = {5};
        double ans = solver.findMedianSortedArrays(longArr, shortArr);
        // 合并后长度 102 -> 取第51与第52再平均
        int[] merged = new int[longArr.length + shortArr.length];
        System.arraycopy(longArr, 0, merged, 0, 3); // 0,2,4
        merged[3] = 5;
        System.arraycopy(longArr, 3, merged, 4, longArr.length - 3);
        java.util.Arrays.sort(merged);
        double baseline = (merged[merged.length / 2 - 1] + merged[merged.length / 2]) / 2.0;
        System.out.println("输入: 长数组(101) & 短数组(1) -> 输出: " + ans + " (期望: " + baseline + ")");
        assertDoubleEquals(ans, baseline, 1e-9, "长度差异极大失败");
        System.out.println("✓ 长度差异极大测试通过");
    }

    private static void testInterleaving(S38_Hard_4_寻找两个正序数组的中位数 solver) {
        int[] a = {1, 3, 5, 7, 9};
        int[] b = {2, 4, 6, 8, 10};
        double ans = solver.findMedianSortedArrays(a, b); // 合并后中位数 5.5
        System.out.println("输入: 交错数组 -> 输出: " + ans + " (期望: 5.5)");
        assertDoubleEquals(ans, 5.5, 1e-9, "交错数组失败");
        System.out.println("✓ 交错数组测试通过");
    }
}
